package com.xucy.springboot.code;

import java.util.*;

/**
 * @Author xucy
 * @Date 2019-10-09 17:24
 * @Description
 **/

public class Test2 {
    String name;

    public Test2(){
        System.out.println("1");
    }

    public Test2(String name){
        System.out.println("2");
        this.name=name;
    }

    public static int[] twoSum(int[] nums, int target) {
        Map map=new HashMap();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{i,Integer.parseInt(map.get(target-nums[i])+"")};
            }else{
                map.put(nums[i],i);
            }
        }
        return new int[]{0,0};
    }

    //盛最多的水 leetcode-11
    public  static int maxArea(int[] height) {
        int maxArea=0;
        for(int i=0;i<height.length-1;i++){
            for(int j=i+1;j<height.length;j++){
                maxArea=Math.max(maxArea,Math.min(height[i],height[j])*(j-i));
            }
        }
        return maxArea;
    }

    //盛最多的水 leetcode-11
    public  static int maxArea2(int[] height) {
        int maxArea=0 ,l=0,r=height.length-1;

        while (l<r){
            maxArea=Math.max(maxArea,Math.min(height[l],height[r])*(r-l));
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return maxArea;
    }

    //三数之和 leetcode-15 时间复杂度 n的3次方
    public static List<List<Integer>> threeSum(int[] nums) {

        List list=new ArrayList();
        if(nums.length<=3){
            return null;
        }

        for(int i=0;i<nums.length-2;i++){
            for(int j=i+1;j<nums.length-1;j++){
                for(int z=j+1;z<nums.length;z++){
                   if(nums[i]+nums[j]+nums[z]==0){
                        List<Integer> list1=new ArrayList<>();
                        list1.add(nums[i]);
                        list1.add(nums[j]);
                        list1.add(nums[z]);
                        list.add(list1);
                   }
                }
            }
        }
        return list;
    }

    //三数之和 leetcode-15
    public static List<List<Integer>> threeSum1(int[] nums) {

        if(nums.length<=3){
            return null;
        }

        List<List<Integer>> list=new ArrayList();
        //排序
        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++){
            int num = nums[i];
            if(num>0) break;
            //去重复
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }

            int l=i+1;
            int r=nums.length-1;
            while (l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum==0){
                    list.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while (l<r && nums[l]==nums[l+1]){l++;}
                    while (l<r && nums[r]==nums[r-1]){r--;}
                    l++;
                    r--;
                }else if(sum<0){
                    l++;
                }else if(sum>0){
                    r--;
                }

            }
        }


        return list;
    }

    //最接近的三数之和 leetcode-16
    public static int threeSumClosest(int[] nums, int target) {
        if(nums.length<3){
            return 0;
        }
        Arrays.sort(nums);
        int abs=nums[0]+nums[1]+nums[2];
        for(int i=0;i<nums.length-2;i++){
            int l=i+1;
            int r=nums.length-1;
            while (l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(Math.abs(target-abs)>Math.abs(target-sum)){
                    abs=sum;
                }
                if(sum>target){
                    r--;
                }else if(sum<target){
                    l++;
                }else{
                    return abs;
                }

            }
        }


        return abs;
    }
    //四数之和 leetcode-18
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list=new ArrayList();
        if(nums.length<4){
            return list;
        }

        Arrays.sort(nums);

        for(int i=0;i<nums.length-3;i++){

            if(i>0&&nums[i]==nums[i-1]){
                continue;//去重
            }
            for(int j=i+1;j<nums.length-2;j++){
                if(j>i+1 && nums[j]==nums[j-1])//去重
                    continue;

                int left=j+1;

                int right=nums.length-1;
                while (left<right){
                    if(nums[right]<target/4)//最大的都小于targer的1/4，后面的不用看了
                        break;
                    int ss=nums[i]+nums[j]+nums[left]+nums[right];
                    if(ss==target){
                        list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while (left<right && nums[right]==nums[right-1]) right--;
                        while (left<right && nums[left]==nums[left+1]) left++;
                        right--;
                        left++;
                    }else if(ss>target){
                        while (left<right && nums[right]==nums[right-1]) right--;
                        right--;
                    }else{
                        while (left<right && nums[left]==nums[left+1]) left++;
                        left++;
                    }
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
//        new Child("li");


//        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15},18)));
//
//        System.out.println(maxArea(new int[]{1,8,6,2,5,4,8,3,7}));
//        System.out.println(maxArea2(new int[]{1,8,6,2,5,4,8,3,7}));
//        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
//        System.out.println(threeSum1(new int[]{-1, 0, 1, 2, -1, -4}));
//        System.out.println(threeSumClosest(new int[]{1,2,4,8,16,32,64,128,82},82));
        System.out.println(fourSum(new int[]{1,-2,-5,-4,-3,3,3,5},-11));
    }
}

